package impl.sort;

import anaydis.sort.SorterType;

import java.util.Comparator;
import java.util.List;

/**
 * Created by IntelliJ IDEA.
 * User: Tomi
 * Date: 24/10/2011
 * Time: 18:16:00
 * To change this template use File | Settings | File Templates.
 */
public class HeapTernarySorter extends AbstractSorter {
    private int size;
    public HeapTernarySorter() {
        super(SorterType.HEAP_TERNARY);
        size = 0;
    }
    public <T> void sort(Comparator<T> c, List<T> list) {
        tree(c, list);
        order(c, list);
    }
    private <T> void tree(Comparator<T> c, List<T> list) {
        size = list.size();
        for(int i=1; i<size; i++){
            int p = padre(i);
            int a = 0;
            if(i>=4){
                a = padre(p);
            }
            final int j = i;
            if(greater(c, list, i, p)){
                swap(list, i, p);
                while(i>3){
                    i = p;
                    p = padre(p);
                    if(greater(c, list, i, p)){
                        swap(list, i, p);
                    }else{
                        break;
                    }
                }
                i = j;
            }
        }
    }
    private <T> void order(Comparator<T> c, List<T> list) {
        while(size>1){
            swap(list, 0, size-1);
            size--;
            sink(c, list, 0);
        }
    }
    private <T> void sink(Comparator<T> c, List<T> list, int k) {
        while((3*k)+1<size){
            int j = (3*k)+1;
            if(j<size-1 && j+1<size && greater(c, list, j+1, j)){
                j++;
                if(j+1<size && greater(c, list, j+1, j)){
                    j++;
                }
            }else if(j<size-1 && j+2<size && greater(c, list, j+2, j)){
                j += 2;                
            }
            if(greater(c, list, k, j)){
                break;
            }
            swap(list, k, j);
            k = j;
        }
    }
    private int padre(int i) {
        int j = i;
        while(j%3!=0){
            j++;
        }
        return (j/3)-1;
    }
}